#include<mpi.h>
#include<stdio.h>
#include <sys/time.h>
#include <time.h>
#include <stdlib.h>

struct timeval t1,t2;//timers
int ARR_SIZE = 10000;
int ARR_LEN = 10000;
int arr[10000][10000];
int arr1[10000][10000];

//均衡初始化
void init() {
	srand((unsigned)time(NULL));
	for (int i = 0; i < ARR_SIZE; i++) {
		for (int j = 0; j < ARR_LEN; j++) {
			arr[i][j] = rand();
		}
	}

}
//负载不均衡初始化
void init1(int rank, int size) {
	srand((unsigned)time(NULL));
	int ratio;
	int seg = ARR_SIZE / size;
	int number = ARR_SIZE / size;
	for (int i = rank * number; i < (rank + 1) * number; i++) {
		if (i < seg) ratio = 0;
		else if (i < seg * 2) ratio = 32;
		else if (i < seg * 3) ratio = 64;
		else if (i < seg * 4) ratio = 128;
		else if (i < seg * 5) ratio = 256;
		else if (i < seg * 6) ratio = 512;
		else if (i < seg * 7) ratio = 1024;
		else if (i < seg * 8) ratio = 2048;
		else ratio = 4096;
		if ((rand() & 4095) < ratio)
			for (int j = 0; j < ARR_LEN; j++) {
				arr1[i][j] = ARR_LEN - j;
			}

		else for (int j = 0; j < ARR_LEN; j++) {
			arr1[i][j] = j;
		}
	}
}
int comp(const void* a, const void* b)
{
	return *(int*)a - *(int*)b;
}
//排序算法
void arr_sort1(int rank, int size) {
	int number = ARR_SIZE / size;
	for (int i = number * rank; i < (number + 1) * rank; i++) {
		qsort(arr1[i], 10000, sizeof(int), comp);
	}
}
int main(int argc, char* argv[])
{
	int size, rank;
	init();
	int temp1 = 0;
	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	gettimeofday(&t1,NULL);
	init1(rank, size);
	arr_sort1(rank, size);
	if (rank == 0) {
		for (int i = 1; i < size; i++) {
			//接收所有非零进程
			MPI_Recv(&temp1, 1, MPI_INT, i, 99, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
		}
		gettimeofday(&t2,NULL);
	    printf("total time :%f ms\n",((t2.tv_sec-t1.tv_sec) * 1000000 + t2.tv_usec-t1.tv_usec)/1e3);
	}
	else {
		//非零进程发送给0号进程
		MPI_Send(&temp1, 1, MPI_INT, 0, 99, MPI_COMM_WORLD);
	}
	MPI_Finalize();
}

